﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;
/*
 * 根据这个论文
Evaluating the state probabilities of M out of N sliding window detectors 
*/
namespace EvaluateMN2
{

    public class Hexad
    {
        //public UInt32 H { get; set; }       // 状态值. 默认全F为*
        public double P { get; set; }       // 该状态概率
        public UInt32 H_plus { get; set; }  // 收到正的值后的H+值
        public UInt32 H_minus { get; set; } // 收到负的值后的H-值
        public double P_plus { get; set; }  // 上一个状态（上一个状态满足收到正值后变为H）的概率
        public double P_minus { get; set; } // 上一个状态（上一个状态满足收到负值后变为H）的概率

        public Hexad(double p = 0, UInt32 hplus = 0, UInt32 hminus= 0, double pplus = 0, double pminus = 0)
        {
            //H = h;
            P = p;
            H_plus = hplus;
            H_minus = hminus;
            P_plus = pplus;
            P_minus = pminus;
        }

    }


    public class EvaluateMN
    {
        //key:H
        public Dictionary<UInt32,Hexad> SetsOfMN = new Dictionary<UInt32, Hexad>();

        List<double> SetsOfP = new List<double>();  // 存储刚好在某个时刻检测到结果的概率
        double lstp = 0.0; // 上一个时刻概率
        public UInt32 M { get; set; }

        public UInt32 N { get; set; }

        public UInt32 size;

        public EvaluateMN(UInt32 m, UInt32 n)
        {
            M = m;
            N = n;
        }

        public void Init2()
        {
            
            UInt32 maxv = UInt32.MaxValue >> (int)(32 - N + 1);
            SetsOfMN[0] = new Hexad(1,M==1?UInt32.MaxValue:1,0);

            for (UInt32 H = 1; H <= maxv; H++)
            {
                Hexad hexad = new Hexad(0);
   
                if (OneCount2(H, N - 1) > M - 1)
                {
                    continue;
                }
                else if (OneCount2(H, N - 1) == M - 1)
                {
                    hexad.H_plus = UInt32.MaxValue;
                }
                else
                {
                    
                    hexad.H_plus = ((H << 1) + 1) & (UInt32.MaxValue >> (int)(32 - N + 1));
                }

                hexad.H_minus = (H << 1) & (UInt32.MaxValue >> (int)(32 - N + 1));

                SetsOfMN[H] = hexad;
            }
            Hexad end = new Hexad(0, UInt32.MaxValue, UInt32.MaxValue, 0, 0);
            SetsOfMN[UInt32.MaxValue] =end;
        }

        public UInt32[] dic = new UInt32[(UInt32.MaxValue >> (int)(32 - 20 + 1)) + 2];
        public void setdic()
        {
            for (int i = 0; i < dic.Length; i++)
                dic[i] = 200;
        }
        public UInt32[] countofone = new UInt32[(UInt32.MaxValue >> (int)(32 - 20 + 1)) + 2];
        public void setcout()
        {
            for (uint i = 0; i < countofone.Length; i++)
                countofone[i] = OneCount2(i, N - 1);
        }

        public void Init3()
        {
            UInt32 mm = M;
            UInt32 nn = N;
            UInt32 maxv = UInt32.MaxValue >> (int)(32 - nn + 1);
           
            setdic();
            setcout();
            
            SetsOfMN[0] = new Hexad(1, mm == 1 ? UInt32.MaxValue : 1, 0);
            
            
            if (mm > 1)
            {
                funct_2(1,mm,nn);
            }
            Hexad end = new Hexad(0, UInt32.MaxValue, UInt32.MaxValue, 0, 0);
            SetsOfMN[UInt32.MaxValue] = end;
        }


        public void funct_2(UInt32 H, UInt32 mm, UInt32 nn)
        {
            Queue<UInt32> ququ = new Queue<UInt32>();
            ququ.Enqueue(H);
            while (ququ.Count > 0)
            {
                UInt32 X = ququ.Dequeue();
                UInt32 plus;
                UInt32 minus;
                if (countofone[X] > mm - 1)
                {
                    return;
                }
                else if (countofone[X] == mm - 1)
                {
                    plus = UInt32.MaxValue;
                }
                else
                {
                    UInt32 np = ((X << 1) + 1) & (UInt32.MaxValue >> (int)(32 - nn + 1));
                    plus = funcseven_2(np, mm, nn);
                }
                UInt32 nm = (X << 1) & (UInt32.MaxValue >> (int)(32 - nn + 1));
                minus = funcseven_2(nm, mm, nn);
                SetsOfMN[X] = new Hexad(0, plus, minus, 0, 0);
                if (plus != UInt32.MaxValue && !SetsOfMN.ContainsKey(plus))
                    ququ.Enqueue(plus);
                if (!SetsOfMN.ContainsKey(minus))
                    ququ.Enqueue(minus);
            }

        }




        public UInt32 funcseven_2(UInt32 n, UInt32 mm, UInt32 nn)
        {
            UInt32 m = n;
            Stack<UInt32> stk = new Stack<UInt32>();
           
            while (countofone[m] < mm - 1)
            {
                stk.Push(m);;
                m = ((m << 1) + 1) & (UInt32.MaxValue >> (int)(32 - nn + 1));
                

            }

            if (countofone[m] == mm - 1)
            {
                
                while (stk.Count != 0)
                {
                    UInt32 pre = stk.Pop();
                    if (m < pre)
                        m = m / 2;
                    else
                        m = pre;
                    
                }
                return m;
            }
            else
                return UInt32.MaxValue;

        }


        public void funct(UInt32 H, UInt32 mm, UInt32 nn)
        {
            //Hexad hxd = new Hexad(0);
            //Console.WriteLine(H);
            UInt32 plus;
            UInt32 minus;
            if (countofone[H] > mm - 1)
                return;
            else if(countofone[H] == mm -1 )
            {
                plus = UInt32.MaxValue;
            }
            else
            {
                UInt32 np = ((H << 1) + 1) & (UInt32.MaxValue >> (int)(32 - nn + 1));
                plus = funcseven(np, mm,nn);// 
            }
            UInt32 nm = (H << 1) & (UInt32.MaxValue >> (int)(32 - nn + 1));
            minus = funcseven(nm, mm,nn); 
            SetsOfMN[H] = new Hexad(0,plus,minus,0,0);
            if (plus != UInt32.MaxValue && !SetsOfMN.ContainsKey(plus))
                funct(plus, mm, nn);
            if (!SetsOfMN.ContainsKey(minus))
                funct(minus, mm, nn);
        
            
        }
       

        

        public UInt32 funcseven(UInt32 n, UInt32 mm, UInt32 nn)
        {
            
            if (countofone[n] == mm - 1)
            {
                dic[n] = UInt32.MaxValue;
                return n;
            }
                
            else
            {
                UInt32 m = ((n << 1) + 1) & (UInt32.MaxValue >> (int)(32 - nn + 1));
                UInt32 l;
                //Console.WriteLine(size);
                if (dic[m] != 200)
                    l = dic[m];
                else
                {
                    dic[m] = funcseven(m, mm, nn);
                    l = dic[m];
                }
                if (l < n)
                    return l / 2;
                else
                    return n;
            }
        }

        void print(UInt32[] x, uint a)
        {

            for (int i = 0; i < a; i++)
            {
                Console.Write("[");

                {

                    Console.Write(x[i]);


                }
                Console.WriteLine("]");

            }
        }

        /// <summary>
        /// 初始化
        /// </summary>
        public void Init()
        {
            Hexad hexad= new Hexad();

            AddHexad(0,hexad);

            hexad.P = 1;
        }

        /// <summary>
        /// 递归函数
        /// </summary>
        /// <param name="hexad"></param>
        private void AddHexad(UInt32 H, Hexad hexad)
        {
            SetsOfMN[H] = hexad;

            if (H == UInt32.MaxValue)
            {
                hexad.H_plus = UInt32.MaxValue;
                hexad.H_minus = UInt32.MaxValue;
                return;
            }
                
            if (OneCount2(H, N-1) == M - 1)
            {
                hexad.H_plus = UInt32.MaxValue;//* state
            }
            else
            {
                hexad.H_plus = ((H << 1) + 1) & (UInt32.MaxValue >> (int)(32-N+1));
            }

            hexad.H_minus = (H << 1) & (UInt32.MaxValue >> (int)(32 - N+1));

            bool find = SetsOfMN.Keys.Contains(hexad.H_plus);
            if (!find)
            {
                Hexad newHexad = new Hexad();
                AddHexad(hexad.H_plus, newHexad);
            }
            find = SetsOfMN.Keys.Contains(hexad.H_minus);
            if (!find)
            {
                Hexad newHexad = new Hexad();
                AddHexad(hexad.H_minus, newHexad);
            }
        }


        static UInt32 OneCount2(UInt32 v, UInt32 windowSize)
        {
            v &= UInt32.MaxValue >> (int)(32 - windowSize);
            v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
            v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
            v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
            v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
            v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
            return v;
        }


        public void Run(double prob)
        {
            int loopcnt = 0;
            int numb = SetsOfMN.Count();
            while(true)
            {
                foreach(var k in SetsOfMN.Keys)
                {
                    SetsOfMN[k].P_minus = SetsOfMN[k].P_plus = 0;
                }
                foreach (var k in SetsOfMN.Keys)
                {
                    SetsOfMN[SetsOfMN[k].H_plus].P_plus += SetsOfMN[k].P;
                    SetsOfMN[SetsOfMN[k].H_minus].P_minus += SetsOfMN[k].P;
                }
                foreach (var k in SetsOfMN.Keys)
                {
                    SetsOfMN[k].P = prob * SetsOfMN[k].P_plus + (1-prob) * SetsOfMN[k].P_minus;
                }
                Console.WriteLine($"{loopcnt}: {SetsOfMN[UInt32.MaxValue].P}");//{SetsOfMN[UInt32.MaxValue].P - lstp}
                lstp = SetsOfMN[UInt32.MaxValue].P;
                loopcnt++;
            }
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            //double k = Math.Pow(2, 19) - 12 * 17 * 19 - 3 * 17 * 19 - 19 * 9 - 20;
            //Console.WriteLine(k);
            var ev = new EvaluateMN(15, 20);
            
            ev.Init2();
            //ev.Init3();
            ev.Run(0.9);
            Console.WriteLine(ev.SetsOfMN.Count());
            Console.ReadLine();
        }
    }
}
